'''
https://leetcode.cn/problems/house-robber-ii/
'''
from functools import cache
from typing import List

class Solution:
    def rob(self, nums: List[int]) -> int:
        n = len(nums)
        if n == 1: return nums[0]
        @cache
        def f(i, canlast):
            if i >= n:
                return 0
            if i == n - 1:
                return nums[i] if canlast else 0
            return max(nums[i] + f(i+2, canlast), f(i+1, canlast))
        return max(f(0, False), f(1, True))

    def rob2(self, nums: List[int]) -> int:
        n = len(nums)
        if n == 1: return nums[0]
        @cache
        def f(i, n):
            if i >= n:
                return 0
            return max(nums[i] + f(i+2, n), f(i+1, n))
        return max(f(0, n-1), f(1, n))

    # DP 打表
    def rob3(self, nums: List[int]) -> int:
        n = len(nums)
        dp1 = [0] * (n + 2)
        dp2 = [0] * (n + 2)
        dp1[-3] = nums[-1]
        # dp2[-3] = 0
        for i in range(n-1, 0, -1):
            dp1[i] = max(nums[i] + dp1[i+2], dp1[i+1])
        for i in range(n-2, -1, -1):
            dp2[i] = max(nums[i] + dp2[i+2], dp2[i+1])
        return max(dp1[1], dp2[0])

    # 状态压缩
    def rob4(self, nums: List[int]) -> int:
        n = len(nums)
        if n == 1: return nums[0]
        a1 = b1 = 0
        for i in range(n-1, 0, -1):
            c = max(nums[i] + b1, a1)
            b1 = a1
            a1 = c
        a2 = b2 = 0
        for i in range(n-2, -1, -1):
            c = max(nums[i] + b2, a2)
            b2 = a2
            a2 = c
        return max(a1, a2)
